#pragma once
#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include "bitset.hpp"
using namespace std;

namespace test
{

struct BKDRHash {
    size_t operator()(const string& s) {
        int val = 0;
        for (auto e : s) val = val * 131 + e;
        return val;
    }
};
struct APHash {
  	size_t operator()(const string& s) {
		size_t hash = 0;
        size_t ch = 0, i = 0;
        for (auto ch : s)
        {
            if (i & 1 == 0)
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            else
                hash ^= (~(hash << 11) ^ ch ^ (hash >> 5));
            i++;
        }
        return hash;
    }
};
struct DJBHash {
  	size_t operator()(const string& s) {
        size_t hash = 5381;
        for (auto ch : s)
            hash += (hash << 5) + ch;
        return hash;
    }
};

template <size_t N,
          size_t MUL = 4,
          class K = string,
          class Hash1 = BKDRHash,
          class Hash2 = APHash,
          class Hash3 = DJBHash>
class bloom_filter
{
public:
    void set(const K& key)
    {
        size_t i1 = Hash1()(key) % _len;
        size_t i2 = Hash2()(key) % _len;
        size_t i3 = Hash3()(key) % _len;
        _bs.set(i1);
        _bs.set(i2);
        _bs.set(i3);
        //cout << i1 << " " << i2 << " " << i3 << endl;
    }

    bool test(const K& key)
    {
        size_t i1 = Hash1()(key) % _len;
        size_t i2 = Hash2()(key) % _len;
        size_t i3 = Hash3()(key) % _len;
        return _bs.test(i1) && _bs.test(i2) && _bs.test((i3));
    }

private:
    bitset<N * MUL> _bs;
    size_t _len = MUL * N;
};

void test_bloom_filter()
{
    bloom_filter<100> bf;

    bf.set("sort");
    bf.set("bloom");
    bf.set("hello world");
    bf.set("abc");
    bf.set("acb");

    cout << bf.test("sort") << endl;
    cout << bf.test("bloom") << endl;
    cout << bf.test("hello world") << endl;
    cout << bf.test("abc") << endl;
    cout << bf.test("acb") << endl;
}

void test_false_positive_rate()
{
    srand(time(0));
    const size_t N = 100000;
    bloom_filter<N, 5> bf;

    string url = "https://leetcode.cn/problem-list/2cktkvj/";

    for (size_t i = 0; i < N; ++i)
    {
        bf.set(url + to_string(i));
    }

    size_t n1 = 0;
    size_t n2 = 0;

    for (size_t i = 0; i < N; i++)
    {
        string similar = url + to_string(163235 + i);
        string not_similar ="zhihu.com" + to_string(rand() + i);
        if (bf.test(similar)) n1++;
        if (bf.test(not_similar)) n2++;
    }

    cout << "Similar string false positive rate: " << (double)n1/N << endl;
    cout << "Not sim string false positive rate: " << (double)n2/N << endl;
}

}